package com.le.tester.imooc.oldfairy.coding.sorting;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * createTime：2023/5/24 15:28
 * description：通用桶序排序
 */
public class BucketSort1 {

    public List<Integer> sort(List<Integer> list, int k, int max, int min) {

        List<LinkedList<Integer>> linkedLists = new ArrayList<>();

        //返回最后包装的一层
        List<Integer> result = new ArrayList<>();

        int m = max - min + 1;
        QuickSort quickSort = new QuickSort();

        for (int i = 0; i < k; i++) {
            linkedLists.add(new LinkedList<>());
        }

        // 放入桶中
        for (Integer item : list) {
            int key = (item - min) * k / m;
            linkedLists.get(key).add(item);
        }
        //从桶中取出值
        for (int i = 0; i < k; i++) {
            result.addAll(quickSort.sort(linkedLists.get(i)));
        }

        return result;


    }
}
